[CERC2017] Gambling Guide

Description

给定一张 nn 个点 mm 条边的无向图。当你在点 uu 时,你可以花费 11 的费用向系统询问当前可以去哪个点,系统会从点 uu 的所有出边中随机选择一条告诉你。你可以选择去,或者重新花费并询问。初始时刻你在 11 号点,要去 nn 号点。求最少花费的期望。
1n,m3×1051\leq n,m\leq 3\times 10^5

Solution

阅读全文 »

Fibonacci's Magic

Fibonacci\rm Fibonacci 数列的性质很多,有的常考,有的不常考。
这些性质都有可能是解题关键。这里稍作总结。
Fibonacci\rm Fibonacci 的定义很多,本文采取如下的递归定义:

fi={0                         i=01                         i=1fi1+fi2          i2f_i=\begin{cases}

阅读全文 »

AGC002F Leftmost Ball

Description

给你 nn 种颜色的球,每个球有 kk 个,把这 n×kn\times k 个球排成一排,把每一种颜色的最左边出现的球涂成白色(初始球不包含白色),求最终有多少种不同的颜色序列,答案对 109+710^9+7 取模。
1n,k2×1031\leq n,k\leq 2\times 10^3

Solution

阅读全文 »

容斥原理

看了 lsqs\sout{\rm{lsqs}} 的博客才知道自己容斥原理学的不够深
容斥大概是计数中非常重要的了。以前都是式子直接用,核心的层次大抵是没有接触到,证明的过程也很少看。所以总结一些比较基础的知识和证明过程。以后式子用起来希望能更有底气。🙏


原始公式

阅读全文 »

Comet OJ Contest 11 F arewell

Description

给定一张 nn 个点 mm 条边的图,一条边 (u,v)(u,v)13\frac{1}{3} 的概率消失,13\frac{1}{3} 的概率定向成 uvu\rightarrow v13\frac{1}{3} 的概率定向成 vuv\rightarrow u 。求最后的图是 DAG\rm{DAG} 的概率。

n20,mn(n1)2n\leq 20,m\leq \frac{n(n-1)}{2}

Solution

阅读全文 »

神奇的整数划分 DP

一个不会整数划分的 sb 的自救


考虑一个这样的问题:给定 n,mn,m ,求将 mm 划分成不超过 nn 个从 11 开始值域连续的整数的和的方案数。

有一个很明显的做法:设 fi,j,kf_{i,j,k} 表示用了 ii 个数,总和为 jj ,目前最大数为 kk 的方案数。转移比较明显:

阅读全文 »